#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""

class UndirectedGraphNode:
    def __init__(self, x):
        self.label = x
        self.neighbors = []


class Solution:
    """
    @param graph: a list of Undirected graph node
    @param A: nodeA
    @param B: nodeB
    @return:  无向图中的最短路径
    """
    def shortestPath(self, graph, A, B):
        # return self.bfs_search_depth(A, B)
        return self.bi_bfs_search(A, B)

    def bi_bfs_search(self, src, dst):
        queue_src = [src]
        queue_dst = [dst]
        visited_src = set()
        visited_dst = set()

        path = 0

        while queue_src and queue_dst:
            # 选择较小的队列开始广搜, 提升性能
            if len(queue_src) <= len(queue_dst):
                cur_queue = queue_src       # current
                ano_queue = queue_dst       # another

                cur_visited = visited_src
                ano_visited = visited_dst

                ano_node = dst
            else:
                cur_queue = queue_dst       # current
                ano_queue = queue_src       # another

                cur_visited = visited_dst
                ano_visited = visited_src

                ano_node = src

            cur_len = len(cur_queue)
            while cur_len:
                cur_len -= 1
                node = cur_queue.pop(0)

                if node in cur_visited:
                    continue

                if node in ano_queue or node in ano_visited:
                    return path

                cur_visited.add(node)

                for nei in node.neighbors:
                    cur_queue.append(nei)

            path += 1

        return -1

    # =================== 普通广度搜索 =====================
    def bfs_search_depth(self, src, dst):
        queue = [src]
        visited = set()
        path = 0

        while queue:
            que_len = len(queue)

            while que_len > 0:
                que_len -= 1
                node = queue.pop(0)

                if node in visited:
                    continue

                if node is dst:
                    return path

                visited.add(node)
                for nei in node.neighbors:
                    queue.append(nei)

            path += 1

        # 最后遍历完了src的广度搜索, 还没有搜到
        return -1


def main():
    print("start main")
    u1 = UndirectedGraphNode(1)
    u2 = UndirectedGraphNode(2)
    u3 = UndirectedGraphNode(3)
    u1.neighbors = [u2]
    u2.neighbors = [u1, u3]
    u3.neighbors = [u2]
    s = Solution()
    ret = s.shortestPath([u1, u2], u1, u3)
    print(ret)

if __name__ == "__main__":
    main()
